public class HeapOperation {
    public static void main(String[] args) {
        System.out.println("再见！");
    }
}

// 创建大根堆，小根堆类似，堆排序类似
class Heapify<T extends Comparable> {
    protected T[] data;
    protected int count;
    protected int capacity;

    // 构造函数, 通过一个给定数组创建一个最大堆
    // 该构造堆的过程, 时间复杂度为O(n)
    public Heapify(T arr[]) {

        int n = arr.length;

        data = (T[]) new Comparable[n + 1];
        capacity = n;

        for (int i = 0; i < n; i++)
            data[i + 1] = arr[i];
        count = n;
        //从第一个不是叶子节点的元素开始
        for (int i = count / 2; i >= 1; i--)
            shiftDown(i);
    }

    // 由下到上调整堆
    private void shiftUp(int k){
        while(k > 1 && data[k].compareTo(data[k/2]) > 0){
            swap(k, k/2);
            k /= 2;
        }
    }

    // 获得堆顶数据
    private T getMax(){
        assert (count>0);
        return data[1];
    }

    // 获取堆顶并调整
    private T extractMax(){
        assert (count>0);
        T ret = data[1];
        swap(1,count);
        count--;
        shiftDown(1);
        return ret;
    }

    // 插入数据
    private void insert(T item){
        assert count+1 <= capacity;
        data[count++] = item;
        shiftUp(count);
    }

    // 由当前k位置往下调整堆
    private void shiftDown(int k) {
        int j = 0;
        while (k * 2 <= count) {
            if (k * 2 +1 <= count) {
                j = data[k * 2].compareTo(data[(k * 2 + 1)])>0 ? k * 2 : k * 2 + 1;
            }

//            int j = 2 * k; // 在此轮循环中,data[k]和data[j]交换位置
//            if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0)
//                j++;
            // data[j] 是 data[2*k]和data[2*k+1]中的最大值

            if (data[k].compareTo(data[j]) >= 0) break;
            swap(k, j);
            k = j;

        }
    }

    // 数据交换
    private void swap(int k, int j) {
        T tmp = data[k];
        data[k] = data[j];
        data[j] = tmp;
    }
}
